from McTree import *
import sys

def StoyGusfield(tree, verbose=False):
	DFS = [None for i in xrange(0, len(tree.s)+1)]
	LL = list(DFS)
	
	#Traverse is the Depth First Search
	def traverse(node, i):
		if isinstance(node, Leaf):
			DFS[node.pos] = i
			LL[i] = node.pos
			i += 1
		else:
			node.DFSstart = i
			for v in node.edges.itervalues():
				i = traverse(v, i)
			node.DFSstop = i
		return i
	
	traverse(tree.root, 0)
	
	branching = list()
	
	def testChildren(span, fromNode, largest=None):#, DFSspan):
		#global branching, LL, DFS, tree
		for k in xrange(span[0],span[1]):
			# Basic round (aka 2b)	
			#print k,	
			i = LL[k]
			j = i + fromNode.strDepth
			if fromNode.DFSstart <= DFS[j] and DFS[j] < fromNode.DFSstop:
				if not tree.s[i] == tree.s[i + 2* fromNode.strDepth]:
					branching.append((i, fromNode.strDepth, 2, 0))
			# Optimized round (aka 2c)
			if largest is not None: 
				j = LL[k]
				i = j - fromNode.strDepth
				if largest[0] <= DFS[i] and DFS[i] < largest[1]:
					branching.append((i, fromNode.strDepth, 2, 0))
			
	
	#The Stoy-Gusfield
	def optimTraverse(node):
		#global tree
		#global branching
		#global DFS, LL
		#iterate over the children
		if isinstance(node, InnerNode):
			if node.strDepth > 0:
				#collect list LL'(node)
				#that is every subtree except the largest.
				largest = (0,-1)
				for c in node.edges.itervalues():
					if isinstance(c, InnerNode):
						if (largest[1]-largest[0]) <= (c.DFSstop-c.DFSstart):
							largest = (c.DFSstart, c.DFSstop)
				if largest == (0,-1):
					#print 'All children',
					testChildren((node.DFSstart, node.DFSstop), node)
					#print
				else:
					# The children are combined of LL'1 - largest - LL'2, where either LL'1 or LL'2 are empty.
					#print largest, '(%i, %i)' %(node.DFSstart, node.DFSstop), 
					if not largest[0] == node.DFSstart:
						#print 'looking at first bite',
						testChildren((node.DFSstart, largest[0]), node, largest)
					if not largest[1] == node.DFSstop:
						#print 'looking at last bite.',
						testChildren((largest[1], node.DFSstop), node, largest)
					#print
					
			for c in node.edges.itervalues():
				optimTraverse(c)
		
	
	optimTraverse(tree.root)
	#print branching
	
	#rotate
	for (i, l, k, b) in branching:
		if i > 0 and tree.s[i-1] == tree.s[i-1+2*l]:
			branching.append((i-1, l, k, 1))
	
	def tandemsort(x,y):
		res = cmp(x[0],y[0])
		if res == 0:
			res = cmp(x[1],y[1])
		return res
	
	branching.sort(tandemsort)
	
	if verbose == True:
		br = 0
		non = 0
		for (i, l, k, b) in branching:
			print '(%i, %i, %i)' %(i, l, k),
			if b == 0:
				print 'branching'
				br += 1
			else:
				print 'non-branching'
				non += 1
		print br, non
	else:
		br  = filter(lambda x: x[3] == 0, branching)
		non = filter(lambda x: x[3] == 1, branching)
		return len(br), len(non)
	
def main(filename):
	try:
		f = open(filename)
		s = f.read()
		f.close()
	except:
		s = filename
	tree = McTree(s)
	
	#StoyGusfield(tree, True)
	result = StoyGusfield(tree)
	print result[0], result[1]

def help():
	print "Searches for tandem repeats in filename or string using Stoy-Gusfield."
	print "Usage: python StoyGusfield.py <filename|string>"
	print 
	print "Will first attempt to open filename, if failes, searches for tandem repeats in string."
	
if __name__ == '__main__':
	if len(sys.argv) != 2:
		help()
	else:
		main(sys.argv[1])